// https://www.jiuzhang.com/solutions/longest-common-substring/#tag-highlight-lang-cpp

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        if (A.empty() || B.empty()) return 0;
        int max_len = 0;
        // for (; i < A.length(); ++i)
        // {
        //     if (A[i] == B[j]) j++;
        //     else
        //     {
        //         max_len = max(max_len, j);
        //         j = 0;
        //     }
        // }
        // return max_len;
        // 可能是B的子序列，j不需要从0开始
        
        for (int i = 0; i < A.length(); ++i)
        {
            for (int j = 0; j < B.length(); ++j)
            {
                if (A[i] == B[j]) 
                {
                    int len = 1;
                    while ((i + len < A.length()) && (j + len < B.length()) && A[i + len] == B[j + len])
                    {
                        len++;
                    }
                    max_len = max(max_len, len);
                }
            }
        }
        return max_len;
    }
};